#include <stdio.h>
#include "single_linked_list.cpp"

// 给定两个单链表, 找出两个链表的公共节点
LNode* CommonNode(LinkedList L1, LinkedList L2) {
    LNode *ptr1 = L1, *ptr2 = L2;
    int len1 = 0, len2 = 0;
    // 查找两链表长度
    while (ptr1->next != NULL) {
        len1++;
        ptr1 = ptr1->next;
    }
    while (ptr2->next != NULL) {
        len2++;
        ptr2 = ptr2->next;
    }

    ptr1 = L1;
    ptr2 = L2;
    // 将两链表尾部对齐
    if (len1 > len2) 
        // 链表1较长     
        while (len1--)
            ptr1 = ptr1->next;
    else if (len1 < len2)
        while (len2--)
            ptr2 = ptr2->next;

    // 同步查找
    while (ptr1 != ptr2)
    {
        ptr1 = ptr1->next;
        ptr2 = ptr2->next;
    }
    return ptr1;
}

int main() {
    LinkedList L1;
    InitList(L1);

    LinkedList L2;
    InitList(L2);

    // 插入
    ListAppend(L1, 2);
    ListAppend(L1, 5);
    ListAppend(L1, 9);
    ListAppend(L1, 7);
    ListAppend(L1, 3);
    ListAppend(L1, 6);
    PrintList(L1);

    ListAppend(L2, 1);
    ListAppend(L2, 2);
    LNode *l1Node = GetElem(L1,3);
    LNode *l2Node = GetElem(L2,2);
    l2Node->next = l1Node;
    PrintList(L2);

    LNode *res = CommonNode(L1,L2);
    printf("公共开始节点: %d", res->data);

    return 0;
}